Many search engine services, such as Google and Overture, provide for searching for information that is accessible via the Internet. These search engine services allow users to search for display pages, such as web pages, that may be of interest to users. After a user submits a search request (i.e., a query) that includes search terms, the search engine service identifies web pages that may be related to those search terms. To quickly identify related web pages, the search engine services may maintain a mapping of keywords to web pages. This mapping may be generated by “crawling” the web (i.e., the World Wide Web) to identify the keywords of each web page. To crawl the web, a search engine service may use a list of root web pages to identify all web pages that are accessible through those root web pages. The keywords of any particular web page can be identified using various well-known information retrieval techniques, such as identifying the words of a headline, the words supplied in the metadata of the web page, the words that are highlighted, and so on. The search engine service identifies web pages that may be related to the search request based on how well the keywords of a web page match the words of the query. The search engine service then displays to the user links to the identified web pages in an order that is based on a ranking that may be determined by their relevance to the query, popularity, importance, and/or some other measure.
Three well-known techniques for page ranking are PageRank, HITS (“Hyperlink-Induced Topic Search”), and DirectHIT. PageRank is based on the principle that web pages will have links to (i.e., “out links”) important web pages. Thus, the importance of a web page is based on the number and importance of other web pages that link to that web page (i.e., “in links”). Web pages and their links can be represented as a web graph. A web graph represents web sites as vertices of the graph and links between web pages of the web sites as edges between the vertices. The edges are directed to differentiate in links and out links. A web graph can be represented as an adjacency matrix A, where Aij represents the number of out links from web page i to web page j. The importance score wj for web page j can be represented by the following equation:wj=ΣiAijw
This equation can be solved by iterative calculations based on the following equation:ATw=wwhere w is the vector of importance scores for the web pages and is the principal eigenvector of AT.
The HITS technique is additionally based on the principle that a web page that has many links to other important web pages may itself be important. Thus, HITS divides “importance” of web pages into two related attributes: “hub” and “authority.” “Hub” is measured by the “authority” score of the web pages that a web page links to, and “authority” is measured by the “hub” score of the web pages that link to the web page. In contrast to PageRank, which calculates the importance of web pages independently from the query, HITS calculates importance based on the web pages of the result and web pages that are related to the web pages of the result by following in links and out links. HITS submits a query to a search engine service and uses the web pages of the result as the initial set of web pages. HITS adds to the set those web pages that are the destinations of in links and those web pages that are the sources of out links of the web pages of the result. HITS then calculates the authority and hub score of each web page using an iterative algorithm. The authority and hub scores can be represented by the following equations:
      a    ⁡          (      p      )        =                    ∑                  q          ->          p                    ⁢                        h          ⁡                      (            q            )                          ⁢                                  ⁢        and        ⁢                                  ⁢                  h          ⁡                      (            p            )                                =                  ∑                  p          ->          q                    ⁢              a        ⁡                  (          q          )                    where a(p) represents the authority score for web page p and h(p) represents the hub score for web page p. HITS uses an adjacency matrix A to represent the links. The adjacency matrix is represented by the following equation:
      b    ij    =      {                            1                                                    if              ⁢                                                          ⁢              page              ⁢                                                          ⁢              i              ⁢                                                          ⁢              has              ⁢                                                          ⁢              a              ⁢                                                          ⁢              link              ⁢                                                          ⁢              to              ⁢                                                          ⁢              page              ⁢                                                          ⁢              j                        ,                                                0                          otherwise                    
The vectors a and h correspond to the authority and hub scores, respectively, of all web pages in the set and can be represented by the following equations:α=ATh and h=AαThus, a and h are eigenvectors of matrices AT A and AAT. HITS may also be modified to factor in the popularity of a web page as measured by the number of visits. Based on an analysis of click-through data, bij of the adjacency matrix can be increased whenever a user travels from web page i to web page j.
Rank aggregation is a technique that combines results of various rankings on sets of entities (e.g., documents or web pages of a search result) to generate an overall ranking of the entities. For example, a meta-search service may receive a query and submit that query to multiple search engine services. Because the search engine services are likely to find different sets of documents that match the query and to use different ranking functions, the search results of each search engine service will include different documents with different rankings. To combine the results from the different search engine services, the meta-search may use rank aggregation to aggregate the various rankings of the search results to generate an overall ranking.
Rank aggregation can be classified into two categories: score-based aggregation and order-based aggregation. In score-based aggregation, each search engine service provides a score for each entity of its search result. Score-based aggregation combines the scores provided by the search engine services to generate an overall score for each entity and ranks the entities based on the combined scores. In order-based aggregation, each search engine service provides a ranking of the entities within its search result. Order-based aggregation generates an overall ranking based on the ordering of the entities in the rankings without using any score that may be provided by the search engine service.
Order-based aggregation is typically performed without any supervision, that is, without using training data to learn how to weight or combine the orders of the different search engine services. Order-based aggregation includes Borda Count techniques (see, e.g., Dwork, C., Kumar, R., Naor, M., and Sivakumar, D., “Rank Aggregation Methods for the Web,” in Proceedings of the 10th International World Wide Web Conference, 2001, pp. 613-622), median rank aggregation techniques (see, e.g., Fagin, R., Kumar, R., and Sivakumar, D., “Efficient Similarity Search and Classification via Rank Aggregation,” in Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, 2003, pp. 301-312), genetic algorithms (see, e.g., M. M. Sufyan Beg, Nesar Ahmad, “Soft Computing Techniques for Rank Aggregation on the World Wide Web,” World Wide Web—An International Journal, Kluwer Academic Publishers, vol. 6, issue 1, Mar. 2003, pp. 5-22; and M. M. Sufyan Beg, “Parallel Rank Aggregation of the World Wide Web,” Proc. International Conference on Intelligent Sensing and Information Processing (ICISIP—2004), Chennai, India, Jan. 4-7, 2004, IEEE Press, pp. 385-390), fuzzy logic techniques (see, e.g., Ahmad, N. and Beg, M. M. S., “Fuzzy Logic Based Rank Aggregation Methods for the World Wide Web,” in Proceedings of the International Conference on Artificial Intelligence in Engineering and Technology, Malaysia, 2002, pp. 363-368), and Markov Chain techniques (see, e.g., Dwork, C., Kumar, R., Naor, M., and Sivakumar, D., “Rank Aggregation Methods for the Web,” in Proceedings of the 10th International World Wide Web Conference, 2001, pp. 613-622). Because such unsupervised rank-aggregation techniques do not use training data, the accuracy of these techniques is suspect.